/*
 * LinkedList.c
 *
 *  Created on: 2015年6月13日
 *      Author: vincent
 */

#include "LinkedList.h"

#include <stdlib.h>
#include <memory.h>

/**
 * 构造链表元素
 */
LINKED_LIST_ELEMENT* linked_list_element_construct()
{
	LINKED_LIST_ELEMENT* linked_list_element = NULL;
	linked_list_element = malloc(sizeof(LINKED_LIST_ELEMENT));
	if(linked_list_element == NULL) return NULL;
	memset(linked_list_element, 0, sizeof(LINKED_LIST_ELEMENT));
	return linked_list_element;
}

/**
 * 释放链表元素
 */
int linked_list_element_destroy(LINKED_LIST_ELEMENT* linked_list_element)
{
	free(linked_list_element);
	return 0;
}

/**
 * 构造链表
 */
LINKED_LIST* linked_list_construct()
{
	LINKED_LIST* linked_list = NULL;
	linked_list = malloc(sizeof(LINKED_LIST));
	if(linked_list == NULL) return NULL;
	memset(linked_list, 0, sizeof(LINKED_LIST));
	return linked_list;
}

/**
 * 释放链表
 */
int linked_list_destroy(LINKED_LIST* linked_list)
{
	int err = 0;
	while(linked_list->length > 0)
	{
		err |= linked_list_remove_first(linked_list);
	}
	free(linked_list);
	return err;
}

/**
 * 在链表前添加元素
 */
void linked_list_offer_first(LINKED_LIST* linked_list, void* target)
{
	LINKED_LIST_ELEMENT *linked_list_element = linked_list_element_construct();
	if(linked_list_element == NULL) return;
	linked_list_element->target = target;
	linked_list->length++;
	if(linked_list->first != NULL)
	{
		linked_list->first->previous = linked_list_element;
		linked_list_element->next = linked_list->first;
		linked_list->first = linked_list_element;
	}
	else if(linked_list->first == NULL && linked_list->last == NULL)
	{
		linked_list->first = linked_list_element;
		linked_list->last = linked_list_element;
	}
}

/**
 * 在链表后添加元素
 */
void linked_list_offer_last(LINKED_LIST* linked_list, void* target)
{
	LINKED_LIST_ELEMENT *linked_list_element = linked_list_element_construct();
	if(linked_list_element == NULL) return;
	linked_list_element->target = target;
	linked_list->length++;
	if(linked_list->last != NULL)
	{
		linked_list->last->next = linked_list_element;
		linked_list_element->previous = linked_list->last;
		linked_list->last = linked_list_element;
	}
	else if(linked_list->first == NULL && linked_list->last == NULL)
	{
		linked_list->first = linked_list_element;
		linked_list->last = linked_list_element;
	}
}

/**
 * 准备获得链表元素
 */
int linked_list_peek_prepare(const LINKED_LIST* linked_list, void** target)
{
	if(linked_list->length == 0)
	{
		*target = NULL;
		return 1;
	}
	return 0;
}

/**
 * 获得链表第一个元素
 */
int linked_list_peek_first(const LINKED_LIST* linked_list, void** target)
{
	int err = linked_list_peek_prepare(linked_list, target);
	if(err) return err;

	LINKED_LIST_ELEMENT* linked_list_element = linked_list->first;
	*target = linked_list_element->target;
	return 0;
}

/**
 * 获得链表最后一个元素
 */
int linked_list_peek_last(const LINKED_LIST* linked_list, void** target)
{
	int err = linked_list_peek_prepare(linked_list, target);
	if(err) return err;

	LINKED_LIST_ELEMENT* linked_list_element = linked_list->last;
	*target = linked_list_element->target;
	return 0;
}

/**
 * 获得链表第一个元素，并移除之
 */
int linked_list_poll_first(LINKED_LIST* linked_list, void** target)
{
	int err = linked_list_peek_first(linked_list, target);
	if(err) return err;

	return linked_list_remove_first(linked_list);
}

/**
 * 获得链表最后一个元素，并移除之
 */
int linked_list_poll_last(LINKED_LIST* linked_list, void** target)
{
	int err = linked_list_peek_last(linked_list, target);
	if(err) return err;

	return linked_list_remove_last(linked_list);
}

/**
 * 准备移除链表元素
 */
int linked_list_remove_prepare(LINKED_LIST* linked_list)
{
	if(linked_list->length == 0)
	{
		return 1;
	}
	linked_list->length--;
	if(linked_list->length == 0)
	{
		linked_list->first = NULL;
		linked_list->last = NULL;
	}
	return 0;
}

/**
 * 移除链表第一个元素
 */
int linked_list_remove_first(LINKED_LIST* linked_list)
{
	int err = linked_list_remove_prepare(linked_list);
	if(err) return err;

	if(linked_list->length > 0)
	{
		LINKED_LIST_ELEMENT* first = linked_list->first;
		linked_list->first = linked_list->first->next;
		linked_list->first->previous = NULL;
		err = linked_list_element_destroy(first);
	}
	return err;
}

/**
 * 移除链表最后一个元素
 */
int linked_list_remove_last(LINKED_LIST* linked_list)
{
	int err = linked_list_remove_prepare(linked_list);
	if(err) return err;

	if(linked_list->length > 0)
	{
		LINKED_LIST_ELEMENT* last = linked_list->last;
		linked_list->last = linked_list->last->previous;
		linked_list->last->next = NULL;
		err = linked_list_element_destroy(last);
	}
	return err;
}

/**
 * 构造链表迭代器
 */
LINKED_LIST_ITERATOR* linked_list_iterator_construct(LINKED_LIST* linked_list,
		unsigned char iterator_type)
{
	LINKED_LIST_ITERATOR* linked_list_iterator = NULL;
	linked_list_iterator = malloc(sizeof(LINKED_LIST_ITERATOR));
	if(linked_list_iterator == NULL) return NULL;
	linked_list_iterator->linked_list = linked_list;
	linked_list_iterator->iterator_type = iterator_type;
	if(iterator_type == LINKED_LIST_ITERATOR_TYPE_FIRST)
	{
		linked_list_iterator->element = linked_list->first;
	}
	else
	{
		linked_list_iterator->element = linked_list->last;
	}
	return linked_list_iterator;
}

/**
 * 释放链表迭代器
 */
int linked_list_iterator_destroy(LINKED_LIST_ITERATOR* linked_list_iterator)
{
	free(linked_list_iterator);
	return 0;
}
/**
 * 检查是否有下一个元素
 */
int linked_list_iterator_has_next(LINKED_LIST_ITERATOR* linked_list_iterator)
{
	if(linked_list_iterator->linked_list->length == 0) return 0;
	if(linked_list_iterator->element == NULL) return 0;
	return 1;
}
/**
 * 得到当前迭代器的值并指向下一个元素
 */
int linked_list_iterator_next(LINKED_LIST_ITERATOR* linked_list_iterator,
		void** target)
{
	if(!linked_list_iterator_has_next(linked_list_iterator)) return 1;
	if(target != NULL) *target = linked_list_iterator->element->target;
	if(linked_list_iterator->iterator_type == LINKED_LIST_ITERATOR_TYPE_FIRST)
	{
		linked_list_iterator->element = linked_list_iterator->element->next;
	}
	else
	{
		linked_list_iterator->element = linked_list_iterator->element->previous;
	}
	return 0;
}
/**
 * 获得链表中指定位置的元素
 */
LINKED_LIST_ELEMENT* linked_list_get_element(LINKED_LIST* linked_list,
		unsigned int index, unsigned char iterator_type)
{
	if(index >= linked_list->length) return NULL;
	int err = 0;
	LINKED_LIST_ITERATOR *linked_list_iterator = NULL;
	linked_list_iterator = linked_list_iterator_construct(linked_list, iterator_type);
	if(linked_list_iterator == NULL) return NULL;

	int i;
	for(i=0;i<index;i++)
	{
		err = linked_list_iterator_next(linked_list_iterator,  NULL);
		if(err) return NULL;
	}

	LINKED_LIST_ELEMENT* linked_list_element = linked_list_iterator->element;
	err = linked_list_iterator_destroy(linked_list_iterator);
	if(err) return NULL;
	return linked_list_element;
}

/**
 * 获得链表中指定位置的元素
 */
int linked_list_get(LINKED_LIST* linked_list,
		unsigned int index, void** target, unsigned char iterator_type)
{
	LINKED_LIST_ELEMENT* linked_list_element = linked_list_get_element(linked_list, index, iterator_type);
	if(linked_list_element == NULL) return 1;
	* target = linked_list_element->target;
	return 0;
}

/**
 * 设置链表中指定位置的元素
 */
int linked_list_set(LINKED_LIST* linked_list,
		unsigned int index, void* target, unsigned char iterator_type)
{
	LINKED_LIST_ELEMENT* linked_list_element = linked_list_get_element(linked_list, index, iterator_type);
	if(linked_list_element == NULL) return 1;
	linked_list_element->target = target;
	return 0;
}

/**
 * 在链表中指定位置前插入元素
 */
int linked_list_insert(LINKED_LIST* linked_list,
		unsigned int index, void* target, unsigned char iterator_type)
{
	LINKED_LIST_ELEMENT* linked_list_element_current;
	linked_list_element_current = linked_list_get_element(linked_list, index, iterator_type);
	if(linked_list_element_current == NULL) return 1;

	LINKED_LIST_ELEMENT *linked_list_element_new = linked_list_element_construct();
	linked_list_element_new->target = target;
	linked_list->length++;

	linked_list_element_new->next = linked_list_element_current;
	if(linked_list->first == linked_list_element_current)
	{
		linked_list->first = linked_list_element_new;
	}
	else
	{
		linked_list_element_new->previous = linked_list_element_current->previous;
		linked_list_element_new->previous->next = linked_list_element_new;
	}
	linked_list_element_current->previous = linked_list_element_new;

	return 0;
}

/**
 * 删除链表中指定位置的元素
 */
int linked_list_remove(LINKED_LIST* linked_list,
		unsigned int index, void** target, unsigned char iterator_type)
{
	int err = 0;
	LINKED_LIST_ELEMENT* linked_list_element_current;
	linked_list_element_current = linked_list_get_element(linked_list, index, iterator_type);
	if(linked_list_element_current == NULL) return 1;

	if(target != NULL) *target = linked_list_element_current->target;
	err = linked_list_remove_prepare(linked_list);
	if(err) return err;

	if(linked_list->length > 0)
	{
		if(linked_list->first == linked_list_element_current)
		{
			linked_list->first = linked_list_element_current->next;
			linked_list->first->previous = NULL;
		}
		else if(linked_list->last == linked_list_element_current)
		{
			linked_list->last = linked_list_element_current->previous;
			linked_list->last->next = NULL;
		}
		else
		{
			linked_list_element_current->previous->next = linked_list_element_current->next;
			linked_list_element_current->next->previous = linked_list_element_current->previous;
		}
	}
	err = linked_list_element_destroy(linked_list_element_current);
	return err;
}
